A Domino-Covering Problem
I do not remember where I saw this problem.
Problem. Invent a connected shape made out of squares on the square grid that cannot be cut into dominoes (rectangles with sides 1 and 2), but if you add a domino to the shape then you can cut the new bigger shape.
This problem reminds me of another famous and beautiful domino-covering problem.
Problem. Two opposite corner squares are cut out from the 8 by 8 square board. Can you cover the remaining shape with dominoes?
The solution to the second problem is to color the shape as a chess board and check that the number of black and white squares is not the same.
What is interesting about the first problem is that it passes the color test. It made me wonder: Is there a way to characterize the shapes on a square grid that pass the color test, but still can’t be covered in dominoes?
Share:
Oscar Cunningham:
I can’t remember what paper I saw this in, but several examples of regions where the colouring argument fails can be made from “dumbbell” shapes, Get two large regions, one with too many white squares and one with two many black squares and connect them by a thin bridge. There will be a balanced number of colours overall, but one will always be able to find a cut across the bridge that puts too many white squares on one side and black squares on the other.
8 July 2017, 6:52 pmtanyakh:
Oscar, thanks. That makes sense.
8 July 2017, 6:58 pmSimon Rubinstein-Salzedo:
Answer to your final question: Yes, there is: the Hall Marriage Theorem.
8 July 2017, 10:41 pmColin Wright:
Tanya, I spoke about exactly this at G4G many years ago, and submitted a paper. Is that perhaps what you saw?
Best,
Colin.
9 July 2017, 6:09 pmtanyakh:
Colin, can you sent me your paper? I think I saw this puzzle in Russian somewhere recently.
9 July 2017, 9:16 pmimpartial james:
There is a nice algorithm to determine if a simply connected region can be tiled by dominos, which I’ve adapted from https://timo.jolivet.free.fr/docs/ThurstonLectNotes.pdf.
Color the interior squares of R black and white in checkerboard fashion, and check if it passes the color test. If so, pick an arbitrary vertex on the boundary and label it zero. Trace clockwise around the boundary. As you go around, label each vertex with the previous label plus one when you pass a white square, and with the previous label minus one when you pass a black square. Once all the border vertices are labeled, find a vertex v with a minimal label; this will not occur on a corner. Place a domino so v is on the midpoint of its long side. What remains is a smaller region (or regions, if the added domino disconnects the region), so this procedure can be recursively applied to the remainder (really, you don’t need to recompute the border labels, only local adjustments need to be made near the added domino).
10 July 2017, 8:36 pmJames Pfeiffer:
The even/odd test and the color test are both global, but there can be local obstructions too, e.g. a “plus sign” shape as below, no matter what the rest of the region looks like.
_X_
12 July 2017, 1:01 pmXXX
_X_
Colin Wright:
Hi Tanya,
I think I have your email somewhere – I’ll try to find it and send you the paper.
If you can email me then it will be easier … I have the paper to hand.
Cheers,
Colin
27 July 2017, 5:18 amColin Wright:
OK! Papers found and sent. Let me know if I can help further.
Best,
Colin
27 July 2017, 5:39 am